数据库为何又如何走向分布式？
The following article is from 多颗糖 Author 多颗糖
数据库领域图灵奖获得者 Jim Gray 说过：“所有的存储系统最终都会演变成数据库系统。(All storage systems will eventually evolve to be database systems.)”
数据库系统经过几十年演进后，分布式数据库在近几年发展如火如荼，国内外出现了很多分布式数据库创业公司，为什么分布式数据库开始流行？在计算机历史上出现过数百个数据库系统，为什么我们需要分布式数据库？
为何走向分布式数据库
让我们追溯数据库发展历史，看看分布式数据库为何出现。
1960 年代：第一个数据库
1961 年，Charles Bachman 等人设计了第一个计算机数据库管理系统(DBMS)，这个网状模型(Network model)的数据库被称为 IDS（Integrated Data Store）。随后不久，IBM 在 1968 年开发了层次模型(hierarchical model)的数据库 IMS（Information Management System）。这两个数据库都是实验性的先行者。
无论是网状模型还是层次模型，最开始的数据库都非常难用，没有很多我们如今习惯的东西：
没有表，更没有 SQL；
数据粗暴存储，不得不通过指针遍历整个数据结构来进行查询；
逻辑层和物理层并不分离，没有独立的模式(schema)，要增加属性，必须重新加载全部的数据然后转存；
最初的数据库没有独立存储数据，没有任何抽象，这导致开发者需要耗费大量精力来使用。
1970 年代：关系型数据库
到了20世纪70年代，IBM 的研究员 Edgar Frank Codd 看到他周围的程序员每天花费大量时间处理查询、改变模式和思考如何存储数据，于是他创造了今天众所周知的关系模型。
关系模型建立之后，IBM 开启了著名的 System R 进行专项研究，该项目是第一个实现 SQL 和事务的 DBMS。System R 的设计对后来各类数据库产生了积极的影响。
关系模型摆脱了查询和数据存储之间的紧密耦合，查询独立于存储，数据库可以自由地在幕后进行优化，程序员无需知道背后的存储方式，只需要通过 SQL 与数据库进行交互，这对于开发者非常友好。
1978 年 Oracle 发布，点燃了商业数据库的导火线。
20世纪末：走向成熟
接下来的几十年里，数据库进入成长期，一步步走向成熟。早期的层次模型和网状模型消失了，关系型数据库成为主流。SQL 成为数据库标准查询语言，直到今天我们仍然在使用。
数据库商业化也越来越完善，同时开始出现如 PostgreSQL 和 MySQL 等开源数据库。由于大型商业数据库非常昂贵，一些互联网企业开始使用 MySQL 等开源数据库作为替代方案。
2000 年代：NoSQL
21 世纪伊始，互联网走向繁荣，突然间许多公司需要支持越来越多的用户，并且必须 24 * 7 不间断运行服务，为此互联网公司不得不在多台计算机上复制(replication)和分片(shard)存储他们的数据。
分片存储即将表按照某个关键字拆分成多个分片，例如按照年进行拆分，2000 年的数据存储在第一台机器上，2001 年的数据存储在第二台机器上，以此类推。这通常由数据库管理员来完成。同时为了让应用程序不修改代码、无感知地读写分片数据，必须要将一个中间件放到这些分片前面，将应用程序原本的 SQL 转换为支持分片的 SQL。如下图所示。
当然，这类方案也有一些缺点，例如：
不支持跨分片事务；
重新分片是困难的，会成为数据库管理员的噩梦；
Google 等公司如此分片存储数据库，目的是不惜一切代价来获得可扩展性，因为他们需要构建越来越大的应用，服务越来越多的用户。这些事情都是为了追求可扩展性。
为此，这些公司还开发了 NoSQL，不惜放弃了关系模型，放弃了事务，放弃了数据一致性保证（有的 NoSQL 只保证最终一致性）。
前文提到，20世纪70年代 Edgar Frank Codd 为了减轻开发人员心智负担而设计了关系型数据库，而 NoSQL 解决了应用程序所需的可扩展性，但又好似退回到了以前，程序员又要面临 NoSQL 功能不足的问题——也就是 Jim Gray 所说的：“所有的存储系统最终都会演变成数据库系统。”
2010 年代：分布式数据库
为什么要构建分布式数据库呢？通过历史发展分析应该相当清楚了，现有的数据库解决方案给开发者和管理员带来了过重的负担。当你开始一个新的大项目，选择一个单点数据库会牺牲掉未来的可扩展性，选择一个 NoSQL 又会让开发者承受额外的负担来解决问题，并且可能不支持事务等优秀的功能。
分布式数据库试图结合两者优点，构建成为两全其美的系统：既能支持完整的关系模型，又能提供高可扩展性和可用性。分布式数据库常被称为 NewSQL 或 Distributed SQL——无论怎么称呼，都指那些在多台机器运行的数据库。
这不是说 NoSQL 是完全没用的，事实上人们在 NoSQL 上构建了许多成功的系统，但这要困难得多。Google 的分布式数据库 Spanner 论文中有一句话：
We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions.
翻译过来就是：“我们认为最好让应用程序开发者来解决因过度使用事务而导致的性能问题，而不是让开发者总是围绕着缺少事务编写代码。”
也就是说，事务是否会造成性能影响的应该由业务开发者来考虑，而作为一个数据库必须提供事务机制，来满足各种应用常见的需求。
Spanner 论文发表后，开始涌现出许多优秀的开源分布式数据库，其中具有代表性的有：CockroachDB、TiDB、YugabyteDB 和最近开源的 OceanBase 等等。
通过回顾数据库历史进程，我们知道了为什么出现分布式数据库，现在我们要关注如何实现分布式数据库。
如何实现分布式数据库
分布式数据库我们关注：
数据如何在机器上分布；
数据副本如何保持一致性；
如何支持 SQL；
分布式事务如何实现；
当然，本文只会简述分布式数据库的简单原理，许多细节不会涉及，如果你想要深入学习，除了学习源代码外，可以关注笔者的公众号和笔者下半年将要出版的书籍。
数据分布
NewSQL 和 NoSQL 的数据分布是类似的，他们都认为所有数据不适合存放在一台机器上，必须分片存储。因此需要考虑：
如何划分分片？
如何定位特定的数据？
分片主要有两种方法：哈希或范围。
哈希分片将某个关键字通过哈希函数计算得到一个哈希值，根据哈希值来判断数据应该存储的位置。这样做的优点是易于定位数据，只需要运行一下哈希函数就能够知道数据存储在哪台机器；但缺点也十分明显，由于哈希函数是随机的，数据将无法支持范围查询。
范围分片指按照某个范围划分数据存储的位置，举个最简单的例子，按照首字母从 A-Z 分为 26 个分区，这样的分片方式对于范围查询非常有用；缺点是通常需要对关键字进行查询才知道数据处于哪个节点，这看起来会造成一些性能损耗，但由于范围很少会改变，很容易将范围信息缓存起来。
例如下图所示，我们按照关键字划分为三个范围：[a 开头，h 开头)、[h 开头，p 开头)、[p 开头，无穷）。
如下图所示，这样进行范围查询效率会更高。
我们关心的最后一个问题是，当某个分片的数据过大，超过我们所设的阈值时，如何扩展分片？由于有一个中间层进行转换，这也很容易进行，只需要在现有的范围中选取某个点，然后将该范围一分为二，便得到两个分区。
如下图所示，当 p-z 的数据量超过阈值，为了避免负载压力，我们拆分该范围。
显然，这里有一个取舍(trade-off)，如果范围阈值设置得很大，那么在机器之间移动数据会很慢，也很难快速恢复某个故障机器的数据；但如果范围阈值设置得很小，中间转换层可能会增长得非常快，增加查询的开销，同时数据也会频繁拆分。一般范围阈值选择 64 MB 到 128 MB，Cockroachdb 使用 64MB 大小，TiDB 默认阈值为 96 MB 大小。
数据一致性
一个带有“分布式”三个字的系统当然需要容忍错误，为了避免一台机器挂掉后数据彻底丢失，通常会将数据复制到多台机器上冗余存储。但分布式系统中请求会丢失、机器会宕机、网络会延迟，因此我们需要某种方式知道冗余的副本中哪些数据是最新的，
最常见的复制数据方式是主从同步（或者直接复制冷备数据），主节点将更新操作同步到从节点。但这样存在潜在的数据不一致问题，同步更新操作丢失了怎么办？从节点恰好写入失败了怎么办？有时这些错误甚至会永久损坏数据，需要数据库管理员介入。
保持一致性常常会以性能为代价(以后我们会讨论)，因此，大部分 NoSQL 只保证最终一致性，并通过一些冲突处理方案来解决数据不一致。
很多名词没有加以解释，如果你觉得很多名词你不了解，想要了解更多内容，请关注我的公众号，或是期待我下半年将出版的新书。
现有著名的复制数据的算法是我们经常听到的 Paxos、Raft、Zab 或 Viewstamped Replication 等算法。其中，Google 花了数年时间才实现了一个满足生产需要的 Paxos 算法。而 Raft 是一个后起新秀，是斯坦福大学的博士生 Ongaro Diego 基于 Paxos 设计的一个更具理解性的共识算法。Raft 诞生后便席卷了分布式共识算法领域，如今你可以在 Github 搜到许许多多的 Raft 开源实现，把他们 clone 到你的应用中来实现可靠的数据复制吧（千万别真的这么干！）。
Raft 未必真的易于使用，但它已经使得编写具有一致性的系统比以往更容易，具体算法细节不再展开，感兴趣的同学请阅读前文《条分缕析 Raft 共识算法》。
简而言之，Raft 算法只需要超过半数的节点写入成功，即认为本次写操作成功，并返回结果给客户端。发生故障时，Raft 算法可以重新选举领导者，只要少于半数的节点发生故障，Raft 就能正常工作。
Raft 算法可以满足可靠复制数据，同时系统能够容忍不超过半数的节点故障。
在分布式数据库中，一个分片使用一个共识组(consensus group)复制数据，具体的 Raft 共识组称为 Raft 组(Raft group)，Paxos 共识组称为 Paxos 组(Paxos group)。
我从 TiDB 官网中找来一张图，TiDB 将一个分片称为一个 Region，如图中有三个 Raft 组，用来复制三个 Region 的数据。
图片权侵删
软件工程没有银弹，使用共识算法仍然需要面临许多生产问题，例如成员变更、范围分区变更、实现线性一致性等等问题都要去克服。只不过现在我们有了坚实的学术支撑，这样进行复制是正确的。
SQL 表数据 KV 化存储
解决了 KV 存储以后，我们还要想办法用 KV 结构来存储表结构。通常，增删查改可以抽象成如下 5 个 KV 操作（也许可以再多些，但基本就是这些）。
Get(key)
Put(key, value)
ConditionalPut(key, value, exp)
Scan(startKey, endKey)
Del(key)
我们讨论的是 OLTP 类分布式数据库都是行存。我们以 CockroachDB 举例，一个表通常包含行和列，可以将一个表转换成如下结构：
/<table>/<index>/<key>/<column> -> Value
为了可读性使用斜杠来分割字段。/<index>/<key>/ 这部分表示需要每个表必须有一个主键。这样看不大直观，举个例子，对于以下建表语句：
CREATE TABLE test (
id INTEGER PRIMARY KEY,
name VARCHAR,
price FLOAT,
);
转换成 KV 存储如图所示：
当然，这样的存储方式会将 float 等类型通通转换为 string 类型。
除此之外，数据库通常会创建一些非主键索引，主要分为两类：
唯一索引
非唯一索引
唯一索引比较简单，由于值唯一，我们可以通过如下映射：
/<table>/<index>/<key> -> Value
如图所示：
非唯一索引和主键类似，只不过其值为空。如图所示：
上述表数据 KV 化规则已经有些陈旧，CockroachDB 最新的映射规则参阅《Structured data encoding in CockroachDB SQL》。但其中的思想是相似的。
当然，表数据 KV 化并不只有这种方式，TiDB 则按照如下规则进行映射：
该方式没有将每一列拆开存储，方法大同小异，详细内容不再展开，参阅《三篇文章了解 TiDB 技术内幕 - 说计算》。
分布式事务
当我们谈论事务时，永远离不开 ACID。分布式事务中最难保证的是原子性和隔离性。在分布式系统中，原子性需要原子提交协议来实现，例如两阶段提交；而隔离性可以通过两阶段锁或多版本并发控制(MVCC)来实现不同的隔离级别。
分布式数据库们都实现了 MVCC，Google Spanner 设计了 TrueTime 来实现，但 TrueTime 并不开源；TiDB 则基于 Google Percolator 来实现。Cockroach 的分布式事务实现比较复杂，涉及到不少新东西，后面我们会展开来谈。
篇幅原因，分布式事务会作为我们后面讨论的重点方向，在此不再展开。
结语
最终，一个分布式数据库简要架构如下图所示。
开源造福人类，如今涌现了许多优秀的开源分布式数据库，他们都是很好的学习材料，笔者也会在后续文章中继续分享 CockroachDB、TiDB、YugabyteDB 和 OceanBase 的技术细节。感谢这些开源者。
值得一提的是，在数据库领域获得图灵奖的学者不多，一共 Charles Bachman、Edgar Frank Codd、Jim Gray、Michael Stonebraker 四位大师，本文提到了其中前三位。2020 年图灵奖获得者 Jeffrey Ullman 虽然在数据库领域也有所建树，但他是因为编程语言领域（“龙书”）而获奖，而非在数据库领域获奖。无论是学术领域还是工业领域，衷心希望分布式+数据库能加把劲！
参考文献
All storage systems will eventually evolve to be database systems. - Jim Gray
"The hows and whys of a distributed SQL database" by Alex Robinson
《三篇文章了解 TiDB 技术内幕 - 说计算》
Corbett J C, Dean J, Epstein M, et al. "Spanner: Google’s globally distributed database." ACM Transactions on Computer Systems (TOCS), 2013, 31(3): 1-22.
Peng D, Dabek F. "Large-scale incremental processing using distributed transactions and notifications." 2010.
Chandra T D, Griesemer R, Redstone J. "Paxos made live: an engineering perspective."Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.
D. Ongaro and J. Ousterhout. "In search of an understandable consensus algorithm." In USENIX Annual Technical Conference (ATC), pages 305--320, 2014.
- EOF -
看完本文有收获？请转发分享给更多人
关注「大数据与机器学习文摘」，成为Top 1%
点赞和在看就是最大的支持❤️